/*
 * @Author: your name
 * @Date: 2021-11-08 22:26:46
 * @LastEditTime: 2021-11-09 00:00:14
 * @LastEditors: Please set LastEditors
 * @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 * @FilePath: \DAA\dividConquer.c
 */

// O(NlogN)

// -2, 11, -4, 13, -5, -2

// Ans 20
#include <stdio.h>
#include <stdlib.h>

int Max3(int a, int b, int c)
{
    if (a > b)
    {
        /* code */
        if (a > c)
        {
            /* code */
            return a;
        } else {
            return c;
        }
        
    } else {
        if (b > c)
        {
            /* code */
            return b;
        } else {
            return c;
        }
        
    }
    
}

// Left = 0, Right = 5
int MaxSubSum(const int A[], int Left, int Right)
{
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBorderSum, MaxRightBorderSum;
    // 经过左边和右边最大值的情况
    int LeftBorderSum, RightBorderSum;
    int Center, i;

    if (Left == Right)
    {
        /* Base Case */
        if (A[Left] > 0)
        {
            /* code */
            return A[Left];
        } else
        {
            /* code */
            return 0;
        }
    }

    Center = (Left + Right) / 2;
    MaxLeftSum = MaxSubSum(A, Left, Center);
    MaxRightSum = MaxSubSum(A, Center + 1, Right);

    MaxLeftBorderSum = 0;
    LeftBorderSum = 0;
    for ( i = Center; i >= Left; i--)
    {
        /* code */
        LeftBorderSum += A[i];
        if (LeftBorderSum > MaxLeftBorderSum)
        {
            /* code */
            MaxLeftBorderSum = LeftBorderSum;
        }
        
    }

    MaxRightBorderSum = 0;
    RightBorderSum = 0;
    for ( i = Center + 1; i <= Right; i++)
    {
        /* code */
        RightBorderSum += A[i];
        if (RightBorderSum > MaxRightBorderSum)
        {
            /* code */
            MaxRightBorderSum = RightBorderSum;
        }
    }
    
    return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}

int main(int argc, char const *argv[])
{
    int A[] = {-2, 11, -4, 13, -5, -2};
    printf("The Max Sum is: %d\n", MaxSubSum(A, 0, 5));

    return 0;
}